package kyssion.leetcode.num101_150;

import java.util.*;

public class code131_分割回文串 {
    List<List<String>> list = new ArrayList<>();

    public List<List<String>> partition(String s) {
        //这个是满足的每一个集合
        List<String> ll = new ArrayList<>();
        dfs(ll, 0, s);
        return list;
    }

    public void dfs(List<String> ll, int index, String s) {
        if (index == s.length()) {
            list.add(new ArrayList<>(ll));
            return;
        }
        //i从index开始是因为单个字符也是回文子串
        for (int i = index; i < s.length(); i++) {
            //如果是回文
            if (isPalindrome(index, i, s)) {

                //把当前的回文子串s(index,i)加进去
                ll.add(s.substring(index, i + 1));
                dfs(ll, i + 1, s);
                //把加进去的回文子串去处。和上面加进去的回文子串是同一个回文子串。
                ll.remove(ll.size() - 1);
            }

        }
    }

    public boolean isPalindrome(int start, int end, String s) {
        while (start < end) {
            if (s.charAt(start) != s.charAt(end))
                return false;
            start++;
            end--;
        }
        return true;
    }
}
